| 翻訳と辞書 |
| edge contraction ： ウィキペディア英語版 |
edge contraction
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation.
== Definition ==
The edge contraction operation occurs relative to a particular edge, ''e''. The edge ''e'' is removed and its two incident vertices, ''u'' and ''v'', are merged into a new vertex ''w'', where the edges incident to ''w'' each correspond to an edge incident to either ''u'' or ''v''.
More generally, the operation may be performed on a set of edges by contracting each edge (in any order). Contractions may result in a graph with loops or multiple edges.〔Loops may arise when the graph started with multiple edges or, even if the graph was simple, from the repeated application of edge contraction. 〕 These are sometimes deleted in order to stay within the class of simple graphs.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「edge contraction」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|